# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/7/7
# @File : 从上到下打印二叉树（3种题型）.py

#1.最简单 不分行从上往下打印二叉树：BFS体系。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        char = []
        tag = []
        if (not root): return []
        tag.append(root)
        while (tag):
            x = tag.pop(0)
            char.append(x.val)
            if (x.left):
                tag.append(x.left)
            if (x.right):
                tag.append(x.right)
        return char

#2.分行从上往下打印二叉树  比较难的，基于BFS设立结束符的做法，来达到区分每层

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        char = []
        tag = []
        res = []
        if (not root): return []
        tag.append(root)
        tag.append(None)#当行的结束符
        while (tag):
            x = tag.pop(0)
            if (x):
                char.append(x.val)
                if (x.left):
                    tag.append(x.left)
                if (x.right):
                    tag.append(x.right)
            else:#说明遇到结束符，遇到上一行的结束符说明下一行的元素全部进入队列了。所以就可以输出这一行并且给这一行加入结束符。
                 #https://www.acwing.com/problem/content/42/，不止一种确定一行结束的技巧，有用i计数的，有用for循环的。
                res.append(char)
                if (tag): tag.append(None)
                char = []
        return res


#3.之字形打印二叉树 即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
#在上一题的基础上作出稍微修改。用一个变量交叉判断一下每一行就行。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def printFromTopToBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        char = []
        tag = []
        res = []
        if (not root): return []
        tag.append(root)
        tag.append(None)
        i = 0
        while (tag):
            x = tag.pop(0)
            if (x):
                char.append(x.val)
                if (x.left):
                    tag.append(x.left)
                if (x.right):
                    tag.append(x.right)
            else:
                if (i == 0):
                    res.append(char)
                    if (tag): tag.append(None)
                    char = []
                    i = 1
                else:
                    char.reverse()
                    res.append(char)
                    if (tag): tag.append(None)
                    char = []
                    i = 0
        return res






